#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解题思路：本题与买卖股票3类似，只是买卖次数变为k次，所以我们要定义一个列数为2k+1的二维数组
dp[i][0]表示初始状态
dp[i][j+1]表示第(j+2)/2次持有股票状态
dp[i][j+2]表示第(j+3)/2次不持有股票的状态
递推公式为:
dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i])
dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])
*/
int dp(int k,vector<int> prices)
{
    //创建dp数组并进行初始化
    vector<vector<int>> dp(prices.size(),vector<int>(2*k+1));
    dp[0][0] = 0;
    for(int j=0;j<2*k;j+=2)
    {
        dp[0][j+1] = -prices[0];
        dp[0][j+2] = 0;
    }
    //遍历dp数组
    for(int i=1;i<prices.size();i++)
    {
        //内层的递推公式要使用一层循环进行递推
        for(int j=0;j<2*k;j+=2)
        {
            //代表的是持有股票，是由上一次不持有股票的状态递推而来
            dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
            //代表不持有股票，由上一次持有股票的状态递推而来
            dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
        }
    }
    return dp[prices.size()-1][2*k];
}
int main()
{
    cout<<"enter a k:"<<endl;
    int k;
    cin>>k;
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter prices:"<<endl;
    vector<int> prices(number);
    for(int i=0;i<number;i++)
        cin>>prices[i];
    cout<<dp(k,prices);
    return 0;
}